package com.summli.basic.class03;

import java.util.Random;

/**
 * 使用荷兰旗帜的问题+递归：快速排序问题（O(N*logN)）,空间复杂度：O(log（N）)(期望值，快速排序不稳定)
 */
public class Code03_2_PartitionAndQuickSort {

    public static void quickSort(int[] arr){
        if(arr == null || arr.length<2){
            return;
        }
        process(arr,0,arr.length-1);
    }

    private static void process(int[] arr, int l, int r) {
        if(l >= r){
            return;
        }

        // 优化的话，使用随机数，取r
        swap(arr,l+ (int)(Math.random()*(r-l+1)),r);

        int[] mids = partition(arr,l,r);//选择r索引的数据进行快速排序
        process(arr,l,mids[0]-1);
        process(arr,mids[1]+1,r);
    }

    private static int[] partition(int[] arr, int l, int r) {
        if(l>r){
            return new int[]{-1,-1};
        }
        if(l==r){
            return new int[]{l,l};
        }
        int p1 = l - 1;
        int p2 = r;
        int index = l;
        while(index<p2){
            if(arr[index]<arr[r]){
                swap(arr,index++,++p1);
            }else if(arr[index] > arr[r]){
                swap(arr,index,--p2);
            }else{
                index++;
            }
        }
        swap(arr, p2, r);
        return new int[]{p1+1,p2};
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        System.out.println((int)(0-2)/2);
    }
}
